package 剑指offer;

import java.util.Arrays;

public class 剑指Offer54二叉搜索树的第k大节点 {

    public static void main(String[] args) {
        TreeNode root = new TreeNode(5);
        TreeNode ndoe1 = new TreeNode(3);
        TreeNode ndoe2 = new TreeNode(2);
        TreeNode ndoe3 = new TreeNode(4);
        TreeNode ndoe4 = new TreeNode(1);
        TreeNode ndoe5 = new TreeNode(6);
        root.left = ndoe1;
        root.right = ndoe5;
        ndoe1.left = ndoe2;
        ndoe1.right = ndoe3;
        ndoe2.left = ndoe4;
        剑指Offer54二叉搜索树的第k大节点 o = new 剑指Offer54二叉搜索树的第k大节点();
        System.out.println(o.kthLargest(root, 3));
    }
    int index = 0;

    public int kthLargest(TreeNode root, int k) {
        //一遍遍历，一遍构建一颗新的二叉树，创建的这个新的二叉树，大小为k的小顶堆
        int[] arr = new int[k];
        //对二叉搜索树进行先序遍历
        preOrder(root,arr,k);
        //按照升序排列arr，最小得元素就为第k大个元素
        Arrays.sort(arr);
        return arr[0];
    }

    private void preOrder(TreeNode root,int[] arr,int k){
        if(root == null) {
            return;
        }
        //先序；根左右
        //小顶堆，如果有第堆顶打的元素，就加入，然后判断是否下沉操作
        if(index < k){
            arr[index] = root.val;
            index++;
        }else{
            //说明已经保存了k个元素在数组中，此时将数组升序排序
            Arrays.sort(arr);
            if(root.val > arr[0]){
                arr[0] = root.val;
            }

        }
        preOrder(root.left,arr,k);
        preOrder(root.right,arr,k);
    }
}
